<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>数据流中的实时中位数计算</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        
        .card-hover {
            transition: all 0.3s ease;
        }
        
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        
        .text-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
            box-shadow: 0 10px 30px rgba(0,0,0,0.2);
        }
        
        .code-header {
            background: #2d2d2d;
            padding: 10px 20px;
            display: flex;
            align-items: center;
            gap: 8px;
        }
        
        .code-dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
            color: #d4d4d4;
            font-size: 14px;
            line-height: 1.6;
        }
        
        .feature-icon {
            width: 60px;
            height: 60px;
            display: flex;
            align-items: center;
            justify-content: center;
            border-radius: 16px;
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            color: white;
            font-size: 24px;
            margin-bottom: 20px;
        }
        
        .step-number {
            width: 40px;
            height: 40px;
            display: flex;
            align-items: center;
            justify-content: center;
            border-radius: 50%;
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            color: white;
            font-weight: bold;
            flex-shrink: 0;
        }
        
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 40px 0;
        }
        
        .highlight-box {
            background: linear-gradient(135deg, #f093fb 0%, #f5576c 100%);
            padding: 2px;
            border-radius: 12px;
            display: inline-block;
        }
        
        .highlight-content {
            background: white;
            padding: 20px 30px;
            border-radius: 10px;
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <div class="hero-gradient text-white py-20">
        <div class="container mx-auto px-6">
            <div class="max-w-4xl mx-auto text-center">
                <h1 class="text-5xl md:text-6xl font-bold mb-6">
                    数据流中的实时中位数计算
                </h1>
                <p class="text-xl md:text-2xl opacity-90 leading-relaxed">
                    探索如何使用双堆结构在动态数据流中高效计算中位数
                </p>
                <div class="mt-10 flex justify-center gap-4">
                    <div class="bg-white bg-opacity-20 backdrop-blur-sm rounded-lg px-6 py-3">
                        <i class="fas fa-clock mr-2"></i>
                        时间复杂度 O(log n)
                    </div>
                    <div class="bg-white bg-opacity-20 backdrop-blur-sm rounded-lg px-6 py-3">
                        <i class="fas fa-memory mr-2"></i>
                        空间复杂度 O(n)
                    </div>
                </div>
            </div>
        </div>
    </div>

    <!-- Main Content -->
    <div class="container mx-auto px-6 py-16">
        <!-- Introduction -->
        <div class="max-w-4xl mx-auto mb-16">
            <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 text-gradient">核心挑战</h2>
                <p class="text-lg leading-relaxed text-gray-700">
                    在数据流中实时计算中位数是一个挑战，因为数据流是动态的、无界的，且不断更新。为了高效地处理这个问题，我们需要一个能支持高效插入、删除和快速中位数查询的数据结构。一个常见的方法是使用两个堆（最大堆和最小堆）来实现这一目标。
                </p>
            </div>
        </div>

        <!-- Solution Overview -->
        <div class="max-w-6xl mx-auto mb-16">
            <h2 class="text-4xl font-bold text-center mb-12">解决方案概览</h2>
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                    <div class="feature-icon">
                        <i class="fas fa-layer-group"></i>
                    </div>
                    <h3 class="text-2xl font-bold mb-4">最大堆（Max Heap）</h3>
                    <p class="text-gray-700 leading-relaxed">
                        存储数据流中较小的一半元素。堆顶元素是较小部分的最大值，确保我们能快速访问中间位置的候选值。
                    </p>
                </div>
                <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                    <div class="feature-icon">
                        <i class="fas fa-sort-amount-up"></i>
                    </div>
                    <h3 class="text-2xl font-bold mb-4">最小堆（Min Heap）</h3>
                    <p class="text-gray-700 leading-relaxed">
                        存储数据流中较大的一半元素。堆顶元素是较大部分的最小值，与最大堆配合实现中位数的快速计算。
                    </p>
                </div>
            </div>
        </div>

        <!-- Data Structure Visualization -->
        <div class="max-w-6xl mx-auto mb-16">
            <h2 class="text-4xl font-bold text-center mb-12">数据结构可视化</h2>
            <div class="bg-white rounded-2xl shadow-xl p-8">
                <div class="mermaid">
                    graph TB
                        subgraph "数据流"
                            A[新数据] -->|插入| B{分配策略}
                        end
                        
                        subgraph "最大堆"
                            C[较小的一半数据]
                            D[堆顶: 最大值]
                        end
                        
                        subgraph "最小堆"
                            E[较大的一半数据]
                            F[堆顶: 最小值]
                        end
                        
                        B -->|较小值| C
                        B -->|较大值| E
                        C --> D
                        E --> F
                        
                        D -->|中位数计算| G[中位数]
                        F -->|中位数计算| G
                        
                        style A fill:#f9f,stroke:#333,stroke-width:2px
                        style G fill:#9f9,stroke:#333,stroke-width:2px
                </div>
            </div>
        </div>

        <!-- Implementation Steps -->
        <div class="max-w-4xl mx-auto mb-16">
            <h2 class="text-4xl font-bold text-center mb-12">实现步骤</h2>
            
            <div class="space-y-6">
                <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                    <div class="flex items-start gap-6">
                        <div class="step-number">1</div>
                        <div class="flex-1">
                            <h3 class="text-2xl font-bold mb-4">插入元素</h3>
                            <p class="text-gray-700 leading-relaxed mb-4">
                                将新元素插入到最大堆中。如果新元素比最大堆的堆顶还要大，则应该插入到最小堆。调整两个堆的大小，确保它们的元素数量差异不超过1。
                            </p>
                            <div class="highlight-box">
                                <div class="highlight-content">
                                    <p class="text-sm">
                                        <i class="fas fa-lightbulb text-yellow-500 mr-2"></i>
                                        关键点：保持两个堆的平衡是算法正确性的核心
                                    </p>
                                </div>
                            </div>
                        </div>
                    </div>
                </div>

                <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                    <div class="flex items-start gap-6">
                        <div class="step-number">2</div>
                        <div class="flex-1">
                            <h3 class="text-2xl font-bold mb-4">平衡调整</h3>
                            <p class="text-gray-700 leading-relaxed">
                                如果最大堆的大小比最小堆大2个元素，将最大堆的堆顶元素移动到最小堆中。如果最小堆的大小比最大堆大1个元素，则将最小堆的堆顶元素移动到最大堆中。
                            </p>
                        </div>
                    </div>
                </div>

                <div class="bg-white rounded-2xl shadow-xl p-8 card-hover">
                    <div class="flex items-start gap-6">
                        <div class="step-number">3</div>
                        <div class="flex-1">
                            <h3 class="text-2xl font-bold mb-4">计算中位数</h3>
                            <ul class="space-y-3 text-gray-700">
                                <li class="flex items-start">
                                    <i class="fas fa-check-circle text-green-500 mr-3 mt-1"></i>
                                    <span>如果最大堆的大小等于最小堆的大小，中位数是两个堆的堆顶元素的平均值。</span>
                                </li>
                                <li class="flex items-start">
                                    <i class="fas fa-check-circle text-green-500 mr-3 mt-1"></i>
                                    <span>如果最大堆的大小比最小堆大1个元素，中位数是最大堆的堆顶元素。</span>
                                </li>
                            </ul>
                        </div>
                    </div>
                </div>
            </div>
        </div>

        <!-- Code Implementation -->
        <div class="max-w-6xl mx-auto mb-16">
            <h2 class="text-4xl font-bold text-center mb-12">Java 实现代码</h2>
            <div class="code-block">
                <div class="code-header">
                    <div class="code-dot bg-red-500"></div>
                    <div class="code-dot bg-yellow-500"></div>
                    <div class="code-dot bg-green-500"></div>
                    <span class="text-gray-400 ml-4">MedianFinder.java</span>
                </div>
                <pre><code>import java.util.PriorityQueue;

public class MedianFinder {
    // 最大堆（小顶堆，取负值以模拟最大堆）
    private PriorityQueue&lt;Integer&gt; maxHeap;
    // 最小堆
    private PriorityQueue&lt;Integer&gt; minHeap;

    /** 初始化数据结构 */
    public MedianFinder() {
        // 小顶堆，取负值实现最大堆
        maxHeap = new PriorityQueue&lt;&gt;((a, b) -&gt; b - a);
        // 大顶堆
        minHeap = new PriorityQueue&lt;&gt;();
    }

    /** 添加一个数到数据流中 */
    public void addNum(int num) {
        // 先将元素放入最大堆
        maxHeap.offer(num);

        // 将最大堆的最大元素移到最小堆中
        minHeap.offer(maxHeap.poll());

        // 如果最小堆的元素数量多于最大堆，则将最小堆的最小元素移到最大堆中
        if (minHeap.size() &gt; maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    /** 获取中位数 */
    public double findMedian() {
        if (maxHeap.size() &gt; minHeap.size()) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }

    public static void main(String[] args) {
        MedianF